1. Field of the Invention
This invention relates in general to packet networks, and more particularly to a method and apparatus for performing measurement-based admission control using peak rate envelopes.
2. Description of Related Art
Packet networks are fundamental element of the Internet and other IP-based WANs. The Internet is increasingly becoming a medium for converging traffic as diverse as data, video, audio, and voice over IP (VOIP). Multimedia network applications involve real-time transmission of data, voice, and video over networks. Some existing applications are video conferencing, multimedia virtual presentation, video-on-demand, and network games. These applications present new challenges to the current networking technology.
For example, multimedia applications have much higher data volume than email and file transfer. The current Internet does not support bandwidth reservation, therefore there is no guarantee that such amount of bandwidth is available when needed. Further, most multimedia data, especially video, are compressed and encoded to decrease the redundancy of data. This creates Variable Bit Rate (VBR) data, which presents another challenge to the networks because the bandwidth need of an application varies over time. Accordingly, the amount of the reserved bandwidth either has to be the peak bandwidth, i.e., the peak-rate reservation, or has to be changed over time to reflect the variability of traffic. Reserving for the peak bandwidth results in waste of bandwidth because the reserved peak bandwidth is not utilized all the time. However, changing the bandwidth reservation over time is much more difficult to accomplish. In addition, multimedia applications are delay-sensitive and loss-sensitive by nature. Most multimedia applications require an explicit delay bound on their transmitted packets because of delay-sensitivity. For example, the delay bound of a live video transmission is related to the receiver""s latest playback time: if the packets arrive beyond that point, they may be useless for the receiver. The delay bound also varies from one application to another due to the differences in their delay-sensitivities and playback environment setups.
While, ATM was designed with different types of quality of service (QoS) categories in mind, the Internet has historically offered a single level of service, which is often referred to as xe2x80x9cbest effort.xe2x80x9d Best effort service merely ensures that all data packets are treated with equity in the network. However, because of the network dynamics, the Internet does not offer a guaranteed level of service quality, but rather some Internet connections exhibit high levels of congestion that result in poor quality, while other Internet connections exhibit consistent levels of high quality service. Thus, IP, as a connectionless protocol, is not a technology that was initially designed for quality of service. New standards such as RSVP, 802.1q and MPOA are attempting to address this shortcoming, either in various transport environments or native to IP.
To satisfy the QoS requirements of real-time multimedia applications, networks must employ resource reservation and admission control techniques. To develop an admission control method, the necessary prerequisites for being able to promise any QoS in packet networks and what the QoS requirements of different user applications must be defined. Note that the term packet network, as used herein, also covers the term cell network, since a cell is a packet of fixed size.
The QoS in packet networks can be defined with delay, delay variation and packet loss ratio experienced by the packet flow of the user. Any packet network providing explicit QoS promises must somehow take care that the total amount of traffic sharing the same resource, like bandwidth of a link, does not exceed a certain level which would cause buffer overflow or does not require queues that are too long thereby resulting in either violation of packet loss or delay promises. Obviously, conforming to QoS promises is a matter of queue behavior estimation. In order to estimate the behavior of packet queues, the network needs to know something about the statistics of traffic sent through connections. Therefore the user and the network must make some kind of traffic contract, including a description of the traffic source, at least. In the simplest case, the network provides the same QoS for all connections and the traffic contract contains only the source traffic description. In a more sophisticated case, the user specifies the QoS level needed; giving requested upper bounds for the delay, the delay variation and the packet loss. In ATM, the sophisticated contract is being used.
Still, there is a possibility of a violation of QoS promises. The traffic contract itself does not prevent a malicious user from sending more traffic than contracted. If the connection is charged according to the contracted traffic rate, then the violation of the contract is tempting. In the worst case, one malicious user can cause violation of the promised QoS of every connection. To avoid this, the network may perform packet level traffic control.
The main purpose of the connection admission control procedure is to protect the user and the network so that the agreed QoS is achieved and the usage of network is optimized. Thus, the connection admission control is a set of actions taken by the network during the call set-up phase in order to determine whether a connection request can be accepted or rejected. Admission control within the network should effectively control the admitted applications so that the existing applications"" QoS are not violated.
To increase bandwidth usage where multiple flows are competing for network resources, statistical multiplexing is often used. Statistical multiplexing is a bandwidth management feature that makes full use of network""s capacity by dynamically allocating bandwidth to applications only when they actually have traffic to send. This type of multiplexing of traffic streams differs a lot from time division multiplexing currently used in telephone networks. Due to the asynchronous nature of the network, packets from more than one incoming link may arrive concurrently and in that case, the most important packets must be carried and the others must be queued. Basically, networks consist of a number of switches and each switch of a number of queues, and every queue in the network is dependent of several other queues. The role of admission control in the network is to maximize the performance of a switch according to chosen overall policy.
As suggested above, two QoS parameters are fundamental to admission control: maximum delay and the probability of violating the maximum delay. Clearly packets must not be queued longer than the QoS parameters allow. From the queue service rate and the maximum delay allowed, the maximum queue length allowed may be calculated as follows:       maximum    ⁢          xe2x80x83        ⁢    queue    ⁢          xe2x80x83        ⁢    length    =            maximum      ⁢              xe2x80x83            ⁢      delay              service      ⁢              xe2x80x83            ⁢      rate      ⁢              xe2x80x83            ⁢      of      ⁢              xe2x80x83            ⁢      the      ⁢              xe2x80x83            ⁢      queue      
Some buffer space for queue is always needed when the aggregate arrival rate of the connections exceeds the service rate of the queue. The admission control must ensure that the peaks of the aggregate arrival rate results in only a small probability of exceeding the maximum queue length allowed. This probability must be equal to or smaller than the probability of violating the maximum delay. Secondly, the packet loss ration requirements of the connections must be fulfilled.
The admission control ensures that the maximum delay or the packet loss ratio does not exceed given bounds using either preventive admission control or measurement-based admission control. Preventive admission control is a more traditional admission control method that relies on the parameters of the source traffic descriptor and calculates the queue length or cell loss ratio for the case the new connection is accepted.
In contrast, measurement-based admission control (MBAC) measures the current traffic and then calculates the effect of the new connection. Both admission control methods then accept the new connection only if given bounds are not exceeded.
Traditional approaches to resource reservation, however, require that an accurate characterization of each flow be specified at flow setup time, a requirement that, in practice, may be difficult for many xe2x80x9clivexe2x80x9d applications to meet. This is especially problematic for applications that exhibit rate variations over multiple time scales, because this behavior is not adequately characterized by standard traffic models such as the leaky bucket.
Measurement-based service is a technique for supporting applications with ill-specified traffic characteristics. By basing admission control decisions on measured values of traffic parameters rather than a priori client specified guesses, the effects of mistaken client traffic characterizations are largely alleviated, as is the need for a traffic model which captures the exact multiple time scale behavior of each traffic flow.
Previous approaches to measurement-based admission control have employed a number of measurement methodologies to characterize traffic including instantaneous peak rate, the instantaneous rate""s mean and variance or moment generating function, and per-flow statistics. In addition, a number of theoretical techniques have been applied to study various aspects of measurement-based admission control including large deviations theory, Gaussian modeling, Hoeffding bounds, and decision theory.
However, previous approaches to measurement-based admission control do not adequately characterize traffic and capture the aggregate flow""s interval-based behavior. Moreover, Gaussian approximations may not be applicable to the traffic flows thereby causing prior approaches to measurement-based admission control to provide unacceptable QoS.
It can be seen that there is a need for an improved measurement-based connection admission control method and apparatus.
It can also be seen that there is a need for a measurement-based connection admission control method and apparatus that is able to characterize traffic and capture the aggregate flow""s interval-based behavior.
It can also be seen that there is a need for a measurement-based connection admission control method and apparatus that can control QoS for a buffered multiplexer servicing a broad class of underlying traffic types, including cases of moderate numbers of traffic flows in which Gaussian approximations may not be applicable.
To overcome the limitations in the prior art described above, and to overcome other limitations that will become apparent upon reading and understanding the present specification, the present invention discloses a method and apparatus for performing measurement-based admission control using peak rate envelopes.
The present invention solves the above-described problems by providing a peak rate envelope estimator that uses empirical traffic envelopes of the aggregate traffic flow to allocate resources. Connection requests from the user are accepted or denied based upon the empirical traffic envelopes of the aggregate traffic flow.
A method in accordance with the principles of the present invention includes a measuring a packet rate of an aggregate flow to obtain a maximal rate envelope and performing admission control for a new connection based upon the maximal rate envelope.
Other embodiments of a method in accordance with the principles of the invention may include alternative or optional additional aspects. One such aspect of the present invention is that the performing admission control further includes using the maximal flow rate to calculate a schedulability condition and admitting a new connection based upon the schedulability condition.
Another aspect of the present invention is that the method further includes quantifying an uncertainty associated with the schedulability condition.
Another aspect of the present invention is that the quantifying is based upon the variation of a previous maximal rate envelope measurement and uncertainty of a future packet rate.
Another aspect of the present invention is that the uncertainty of the future packet rate is based upon a packet loss probability reflecting a mean number of packets lost when the future arriving packet exceed a past measured maximal rate envelope.
Another aspect of the present invention is that the schedulability condition includes a no packet loss condition for a new flow, bounded by xcfx80k,k=1, . . . T, requesting admission to a first-come-first-serve server with capacity C, buffer size B, and a workload characterized by a maximal rate envelope with mean {overscore (R)}k with variance "sgr"k2,k=1, . . . , T, and a confidence level "PHgr"(a), the no packet loss condition defined according to             max                        k          =          1                ,        2        ,        …        ⁢                  xe2x80x83                ,                  T          -          1                      ⁢          xe2x80x83        ⁢          {              k        ⁢                  xe2x80x83                ⁢                  τ          ⁡                      (                                                            R                  _                                k                            +                              α                ⁢                                  xe2x80x83                                ⁢                                  σ                  k                                            +                              τ                k                            -              C                        )                              }        ≤            B      ⁢              xe2x80x83            ⁢      and      ⁢              xe2x80x83            ⁢                        R          _                T              +          α      ⁢              xe2x80x83            ⁢              σ        T              +          τ      T        ≤      C    .  
Another aspect of the present invention is that             max                        k          =          1                ,        2        ,        …        ⁢                  xe2x80x83                ,                  T          -          1                      ⁢          xe2x80x83        ⁢          {              k        ⁢                  xe2x80x83                ⁢                  τ          ⁡                      (                                                            R                  _                                k                            +                              α                ⁢                                  xe2x80x83                                ⁢                                  σ                  k                                            +                              τ                k                            -              C                        )                              }        ≤  B
ensures that the maximal buffer occupancy is smaller than the buffer size.
Another aspect of the present invention is that {overscore (R)}T+xcex1"sgr"T+xcfx84Txe2x89xa6C is a stability condition for ensuring that the mean rate over intervals of length T is less than link capacity with confidence level "PHgr"(xcex1), so that the busy period is less than T also with probability "PHgr"(xcex1).
Another aspect of the present invention is that the admission control includes checking for an aggregate schedulability condition with an associated prediction confidence level, determining the packet loss probability based upon a measured variance of the maximal rate envelope and admitting a new connection when estimated future performance parameters satisfy requested quality of service requirements.
Another aspect of the present invention is that future performance parameters satisfy requested quality of service requirements if an expected packet loss bounding rate is greater than a predetermined value when the aggregate schedulability condition with an associated confidence level fails to hold.
Another aspect of the present invention is that the packet loss probability for an aggregate traffic flow that satisfies the schedulability condition                     max                              k            =            1                    ,          2          ,          …          ⁢                      xe2x80x83                    ,                      T            -            1                              ⁢              xe2x80x83            ⁢              {                  k          ⁢                      xe2x80x83                    ⁢                      τ            ⁡                          (                                                                    R                    _                                    k                                +                                  α                  ⁢                                      xe2x80x83                                    ⁢                                      σ                    k                                                  +                                  τ                  k                                -                C                            )                                      }              ≤                  B        ⁢                  xe2x80x83                ⁢        and        ⁢                  xe2x80x83                ⁢                              R            _                    T                    +              α        ⁢                  xe2x80x83                ⁢                  σ          T                    +              τ        T              ≤    C    ,
and has mean bounding rate {overscore (R)}k and variance "sgr"k2 over intervals of length kxcfx84, for a link capacity C, buffer size B, and schedulability confidence level "PHgr"(xcex1) is bounded by                     max                              k            =            1                    ,          2          ,          …          ⁢                      xe2x80x83                    ,          T                    ⁢              xe2x80x83            ⁢                                    σ            k                    ⁢          Ψ          ⁢                      xe2x80x83                    ⁢                                    (              α              )                        ·                          I              k                                                                          R              _                        T                    ·                      T            τ                                ≤          P      loss        ≤                  max                              k            =            1                    ,          2          ,          …          ⁢                      xe2x80x83                    ,          T                    ⁢                                    σ            k                    ⁢          Ψ          ⁢                      xe2x80x83                    ⁢                      (            α            )                                                R            _                    T                      ,      
    ⁢            where      ⁢              xe2x80x83            ⁢      Ψ      ⁢              xe2x80x83            ⁢              (        α        )              =                  δ        0            ⁢                        ⅇ                      -                          xe2x80x83                        ⁢                                          α                -                                  λ                  0                                                            δ                0                                                    .            
Another aspect of the present invention is that the maximal rate envelope captures an aggregate flow""s interval based behavior.
Another aspect of the present invention is that the measuring the packet rate updates a recent aggregate envelope and quantifies a temporal variation for the maximal rate envelope.
Another aspect of the present invention is that the measuring the packet rate further including setting an interval length for flow rate measurements and determining a peak packet rate over the set interval length.
These and various other advantages and features of novelty, which characterize the invention, are pointed out with particularity in the claims annexed hereto and form a part hereof. However, for a better understanding of the invention, its advantages, and the objects obtained by its use, reference should be made to the drawings which form a further part hereof, and to accompanying descriptive matter, in which there are illustrated and described specific examples of an apparatus in accordance with the invention.